{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Time Comparison of Three Methods (or however more we add)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find prime numbers up to a given number "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach 1: For Loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def approach1(givenNumber):\n",
    "    \n",
    "    # Initialize a list\n",
    "    primes = []\n",
    "    \n",
    "    for possiblePrime in range(2, givenNumber + 1):\n",
    "        \n",
    "        # Assume number is prime until shown it is not. \n",
    "        isPrime = True\n",
    "        for num in range(2, possiblePrime):\n",
    "            if possiblePrime % num == 0:\n",
    "                isPrime = False\n",
    "        \n",
    "        if isPrime:\n",
    "            primes.append(possiblePrime)\n",
    "    return(primes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,\n",
       " 3,\n",
       " 5,\n",
       " 7,\n",
       " 11,\n",
       " 13,\n",
       " 17,\n",
       " 19,\n",
       " 23,\n",
       " 29,\n",
       " 31,\n",
       " 37,\n",
       " 41,\n",
       " 43,\n",
       " 47,\n",
       " 53,\n",
       " 59,\n",
       " 61,\n",
       " 67,\n",
       " 71,\n",
       " 73,\n",
       " 79,\n",
       " 83,\n",
       " 89,\n",
       " 97,\n",
       " 101,\n",
       " 103,\n",
       " 107,\n",
       " 109,\n",
       " 113,\n",
       " 127,\n",
       " 131,\n",
       " 137,\n",
       " 139,\n",
       " 149,\n",
       " 151,\n",
       " 157,\n",
       " 163,\n",
       " 167,\n",
       " 173,\n",
       " 179,\n",
       " 181,\n",
       " 191,\n",
       " 193,\n",
       " 197,\n",
       " 199,\n",
       " 211,\n",
       " 223,\n",
       " 227,\n",
       " 229,\n",
       " 233,\n",
       " 239,\n",
       " 241,\n",
       " 251,\n",
       " 257,\n",
       " 263,\n",
       " 269,\n",
       " 271,\n",
       " 277,\n",
       " 281,\n",
       " 283,\n",
       " 293,\n",
       " 307,\n",
       " 311,\n",
       " 313,\n",
       " 317,\n",
       " 331,\n",
       " 337,\n",
       " 347,\n",
       " 349,\n",
       " 353,\n",
       " 359,\n",
       " 367,\n",
       " 373,\n",
       " 379,\n",
       " 383,\n",
       " 389,\n",
       " 397,\n",
       " 401,\n",
       " 409,\n",
       " 419,\n",
       " 421,\n",
       " 431,\n",
       " 433,\n",
       " 439,\n",
       " 443,\n",
       " 449,\n",
       " 457,\n",
       " 461,\n",
       " 463,\n",
       " 467,\n",
       " 479,\n",
       " 487,\n",
       " 491,\n",
       " 499]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "approach1(500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach 2: For Loop with Break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only difference is a break statement. Basically once you know that a number isn't prime why should you keep on testing it in the inner loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def approach2(givenNumber):\n",
    "\n",
    "    # Initialize a list\n",
    "    primes = []\n",
    "    for possiblePrime in range(2, givenNumber):\n",
    "\n",
    "        # Assume number is prime until shown it is not. \n",
    "        isPrime = True\n",
    "        for num in range(2, possiblePrime):\n",
    "            if possiblePrime % num == 0:\n",
    "                isPrime = False\n",
    "                break\n",
    "\n",
    "        if isPrime:\n",
    "            primes.append(possiblePrime)\n",
    "    \n",
    "    return(primes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,\n",
       " 3,\n",
       " 5,\n",
       " 7,\n",
       " 11,\n",
       " 13,\n",
       " 17,\n",
       " 19,\n",
       " 23,\n",
       " 29,\n",
       " 31,\n",
       " 37,\n",
       " 41,\n",
       " 43,\n",
       " 47,\n",
       " 53,\n",
       " 59,\n",
       " 61,\n",
       " 67,\n",
       " 71,\n",
       " 73,\n",
       " 79,\n",
       " 83,\n",
       " 89,\n",
       " 97,\n",
       " 101,\n",
       " 103,\n",
       " 107,\n",
       " 109,\n",
       " 113,\n",
       " 127,\n",
       " 131,\n",
       " 137,\n",
       " 139,\n",
       " 149,\n",
       " 151,\n",
       " 157,\n",
       " 163,\n",
       " 167,\n",
       " 173,\n",
       " 179,\n",
       " 181,\n",
       " 191,\n",
       " 193,\n",
       " 197,\n",
       " 199,\n",
       " 211,\n",
       " 223,\n",
       " 227,\n",
       " 229,\n",
       " 233,\n",
       " 239,\n",
       " 241,\n",
       " 251,\n",
       " 257,\n",
       " 263,\n",
       " 269,\n",
       " 271,\n",
       " 277,\n",
       " 281,\n",
       " 283,\n",
       " 293,\n",
       " 307,\n",
       " 311,\n",
       " 313,\n",
       " 317,\n",
       " 331,\n",
       " 337,\n",
       " 347,\n",
       " 349,\n",
       " 353,\n",
       " 359,\n",
       " 367,\n",
       " 373,\n",
       " 379,\n",
       " 383,\n",
       " 389,\n",
       " 397,\n",
       " 401,\n",
       " 409,\n",
       " 419,\n",
       " 421,\n",
       " 431,\n",
       " 433,\n",
       " 439,\n",
       " 443,\n",
       " 449,\n",
       " 457,\n",
       " 461,\n",
       " 463,\n",
       " 467,\n",
       " 479,\n",
       " 487,\n",
       " 491,\n",
       " 499]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "approach2(500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach 3: For Loop, Break, and Square Root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def approach3(givenNumber):  \n",
    "    \n",
    "    # Initialize a list\n",
    "    primes = []\n",
    "    for possiblePrime in range(2, givenNumber + 1):\n",
    "\n",
    "        # Assume number is prime until shown it is not. \n",
    "        isPrime = True\n",
    "        for num in range(2, int(possiblePrime ** 0.5) + 1):\n",
    "            if possiblePrime % num == 0:\n",
    "                isPrime = False\n",
    "                break\n",
    "\n",
    "        if isPrime:\n",
    "            primes.append(possiblePrime)\n",
    "    \n",
    "    return(primes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,\n",
       " 3,\n",
       " 5,\n",
       " 7,\n",
       " 11,\n",
       " 13,\n",
       " 17,\n",
       " 19,\n",
       " 23,\n",
       " 29,\n",
       " 31,\n",
       " 37,\n",
       " 41,\n",
       " 43,\n",
       " 47,\n",
       " 53,\n",
       " 59,\n",
       " 61,\n",
       " 67,\n",
       " 71,\n",
       " 73,\n",
       " 79,\n",
       " 83,\n",
       " 89,\n",
       " 97,\n",
       " 101,\n",
       " 103,\n",
       " 107,\n",
       " 109,\n",
       " 113,\n",
       " 127,\n",
       " 131,\n",
       " 137,\n",
       " 139,\n",
       " 149,\n",
       " 151,\n",
       " 157,\n",
       " 163,\n",
       " 167,\n",
       " 173,\n",
       " 179,\n",
       " 181,\n",
       " 191,\n",
       " 193,\n",
       " 197,\n",
       " 199,\n",
       " 211,\n",
       " 223,\n",
       " 227,\n",
       " 229,\n",
       " 233,\n",
       " 239,\n",
       " 241,\n",
       " 251,\n",
       " 257,\n",
       " 263,\n",
       " 269,\n",
       " 271,\n",
       " 277,\n",
       " 281,\n",
       " 283,\n",
       " 293,\n",
       " 307,\n",
       " 311,\n",
       " 313,\n",
       " 317,\n",
       " 331,\n",
       " 337,\n",
       " 347,\n",
       " 349,\n",
       " 353,\n",
       " 359,\n",
       " 367,\n",
       " 373,\n",
       " 379,\n",
       " 383,\n",
       " 389,\n",
       " 397,\n",
       " 401,\n",
       " 409,\n",
       " 419,\n",
       " 421,\n",
       " 431,\n",
       " 433,\n",
       " 439,\n",
       " 443,\n",
       " 449,\n",
       " 457,\n",
       " 461,\n",
       " 463,\n",
       " 467,\n",
       " 479,\n",
       " 487,\n",
       " 491,\n",
       " 499]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "approach3(500)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "71.88647201500135\n",
      "14.760350739990827\n",
      "4.1344189689843915\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "\n",
    "# Approach 1: Execution time \n",
    "print(timeit.timeit('approach1(500)', globals=globals(), number=10000))\n",
    "\n",
    "# Approach 2: Execution time\n",
    "print(timeit.timeit('approach2(500)', globals=globals(), number=10000))\n",
    "\n",
    "# Approach 3: Execution time\n",
    "print(timeit.timeit('approach3(500)', globals=globals(), number=10000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
